package com.test.sort;

import java.util.Arrays;

/**
 * 选择排序
 */
public class SelectSort extends BaseSort{
    public static void main(String[] args) {
        //1纳秒=0.000001 毫秒=10的负6次方毫秒
        //一秒的10亿分之一，即等于10的负9次方秒。常用作 内存读写速度的单位
        long start = System.nanoTime();
        BaseSort sort = new SelectSort();
        int[] a = {8, 2, 1, 6, 3, 9, 5, 7, 23, 13,27};
        sort.sort(a);
        long end = System.nanoTime();
        System.err.println((end-start)+"纳秒");
        Arrays.stream(a).forEach(System.out::println);
    }

    /**
     * 选择排序
     * 第一轮，找到最小的元素，和数组第一个数交换位置。
     * 第二轮，找到第二小的元素，和数组第二个数交换位置...
     * 直到最后一个元素，排序完成
     *
     * 平均时间复杂度：O(n²)  用了双重for循环
     * 算法空间复杂度：O(1)
     * 算法稳定性：不稳定 ，
     * 原因：在一趟选择，如果当前元素比一个元素小，
     * 而该小的元素又出现在一个和当前元素相等 的元素后面，那么交换后稳定性就被破坏了。
     * 比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，
     * 那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法
     *
     * @param nums
     */
    @Override
    protected void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = nums[i];
                nums[minIndex] = temp;
                nums[i] = nums[minIndex];
            }
        }
    }
}
